|
GNU bison, commonly known as Bison, is a parser generator that is part of the GNU Project. Bison reads a specification of a context-free language, warns about any parsing ambiguities, and generates a parser (either in C, C++, or Java) which reads sequences of tokens and decides whether the sequence conforms to the syntax specified by the grammar. Bison by default generates LALR parsers but can also create GLR parsers. In POSIX mode, Bison is compatible with yacc, but also has several improvements over this earlier program. flex, an automatic lexical analyser, is often used with Bison, to tokenise input data and provide Bison with tokens. Bison was originally written by Robert Corbett in 1988. Later, in 1990, Robert Corbett wrote another parser generator named Berkeley Yacc. Bison was made Yacc-compatible by Richard Stallman. Bison is free software and is available under the GNU General Public License, with an exception (discussed below) allowing its generated code to be used without triggering the copyleft requirements of the licence. ==A complete reentrant parser example== The following example shows how to use Bison and flex to write a simple calculator program (only addition and multiplication) and a program for creating an abstract syntax tree. The next two files provide definition and implementation of the syntax tree functions. / * * Expression.h * Definition of the structure used to build the syntax tree. */ #ifndef __EXPRESSION_H__ #define __EXPRESSION_H__ / * * * @brief The operation type */ typedef enum tagEOperationType EOperationType; / * * * @brief The expression structure */ typedef struct tagSExpression SExpression; / * * * @brief It creates an identifier * @param value The number value * @return The expression or NULL in case of no memory */ SExpression *createNumber(int value); / * * * @brief It creates an operation * @param type The operation type * @param left The left operand * @param right The right operand * @return The expression or NULL in case of no memory */ SExpression *createOperation(EOperationType type, SExpression *left, SExpression *right); / * * * @brief Deletes a expression * @param b The expression */ void deleteExpression(SExpression *b); #endif // __EXPRESSION_H__ / * * Expression.c * Implementation of functions used to build the syntax tree. */ #include "Expression.h" #include / * * * @brief Allocates space for expression * @return The expression or NULL if not enough memory */ static SExpression *allocateExpression() SExpression *createNumber(int value) SExpression *createOperation(EOperationType type, SExpression *left, SExpression *right) void deleteExpression(SExpression *b) The tokens needed by the Bison parser will be generated using flex. % %option outfile="Lexer.c" header-file="Lexer.h" %option warn nodefault %option reentrant noyywrap never-interactive nounistd %option bison-bridge LPAREN "(" RPAREN ")" PLUS "+" MULTIPLY " *" NUMBER ()+ WS (\r\n\t ) * %% . %% int yyerror(const char *msg) Since the tokens are provided by flex we must provide the means to communicate between the parser and the lexer.〔(GNU Bison Manual: C Scanners with Bison Parsers )〕 The data type used for communication, ''YYSTYPE'', is set using Bison's ''%union'' declaration. Since in this sample we use the reentrant version of both flex and yacc we are forced to provide parameters for the ''yylex'' function, when called from ''yyparse''.〔 This is done through Bison's ''%lex-param'' and ''%parse-param'' declarations.〔(GNU Bison Manual: Calling Conventions for Pure Parsers )〕 % %code requires %output "Parser.c" %defines "Parser.h" %define api.pure %lex-param %parse-param %parse-param %union %left '+' TOKEN_PLUS %left ' *' TOKEN_MULTIPLY %token TOKEN_LPAREN %token TOKEN_RPAREN %token TOKEN_PLUS %token TOKEN_MULTIPLY %token %type %% input : expr ; expr : expr() TOKEN_PLUS expr() | expr() TOKEN_MULTIPLY expr() | TOKEN_LPAREN expr() TOKEN_RPAREN | TOKEN_NUMBER ; %% The code needed to obtain the syntax tree using the parser generated by Bison and the scanner generated by flex is the following. / * * main.c file */ #include "Expression.h" #include "Parser.h" #include "Lexer.h" #include int yyparse(SExpression * *expression, yyscan_t scanner); SExpression *getAST(const char *expr) yy_delete_buffer(state, scanner); yylex_destroy(scanner); return expression; } int evaluate(SExpression *e) int main(void) A simple makefile to build the project is the following. # Makefile FILES 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「GNU bison」の詳細全文を読む スポンサード リンク
|